package main

// 合并两个有序数组
// https://leetcode.cn/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150
import "fmt"

func main() {
	m := 3
	n := 3
	nums1 := []int{1, 2, 3, 0, 0, 0}
	// merge1(nums1, m, []int{}, n)
	// fmt.Println(nums1)
	mergeDblPtr(nums1, m, []int{2, 5, 6}, n)
	fmt.Println(nums1)
}

// 双循环，移动结果
func merge1(nums1 []int, m int, nums2 []int, n int) {
	for i := 0; i < n; i++ {
		for j := i; j < m+i+1; j++ {
			if nums2[i] >= nums1[j] {
				if j == m+i {
					nums1[j] = nums2[i]
					break
				}
				continue
			}

			// 移动数组
			copy(nums1[j+1:], nums1[j:])
			nums1[j] = nums2[i]
			break
		}
	}
}

// 双指针
func mergeDblPtr(nums1 []int, m int, nums2 []int, n int) {
	var p1, p2 int
	d := []int{}
	for i := 0; i < m+n; i++ {
		if p1 < m && p2 < n && nums1[p1] < nums2[p2] {
			d = append(d, nums1[p1])
			p1++
		} else if p2 < n {
			d = append(d, nums2[p2])
			p2++
		} else {
			d = append(d, nums1[p1])
			p1++
		}
	}

	copy(nums1[:], d)
}
